A file server is a type of storage server which operates on behalf of one or more clients to store and manage shared files in a set of mass storage devices, such as magnetic or optical storage based disks. The mass storage devices are typically organized as one or more groups of Redundant Array of Independent (or Inexpensive) Disks (RAID). One configuration in which file servers can be used is a network attached storage (NAS) configuration. In a NAS configuration, a file server can be implemented in the form of an appliance, called a filer, that attaches to a network, such as a local area network (LAN) or a corporate intranet. An example of such an appliance is any of the NetApp Filer products made by Network Appliance, Inc. in Sunnyvale, Calif.
An operating system (OS) is the software on a computing system or device such as a storage or file server that is used to control the basic functions of the system. The OS may include a file system to organize and perform operations on data stored on various storage devices, including magnetic and optical devices such as hard drives or compact disc read only memory (CD-ROMs). The file system typically manages the reading and writing of data on storage devices. The term “file system” may also refer to the stored data in its entirety. A file system typically includes tools to verify the accuracy of the stored data.
A file system may organize data stored on a storage device using any one of several techniques. According to one technique, the storage on the storage device is divided into 4-kilobyte (KB) blocks. The blocks are organized into a storage pool, and hold all of the data stored on the storage device, including the data needed to organize files and directories. A single file or other data structure can be represented by a data structure known as an inode. The inode includes block pointers that point to the location of the blocks for a file. The file system can find the locations of the data blocks that compose a specific file by determining the inode that corresponds to the file, and following the pointers in the inode to the blocks that store the data.
The allocation of the blocks is sometimes tested to make sure that each block is properly allocated and that pointers to the block are proper. This type of testing is particularly important in a storage server, such as a file server, which maintains large volumes of data on behalf of multiple clients. For example, the testing may determine that a block listed as being unused is in fact used. The testing is done to insure the integrity of the data stored on the storage device.
At least one previous method for testing block allocation allotted five bits for each block. The five bits formed a block record. Two bits of the record determined whether certain attributes had been set and the remaining three bits listed the usage of the block. The block records were all stored in memory, during which time the method tried to determine whether the allocation was proper.
Since storage devices may be very large, a computer system may not have enough memory to test all of the blocks at once. As a result, the storage pool on the computer system is divided into several different passes. While the scan of the file system is occurring, the storage is inaccessible. Therefore, it is advantageous to minimize the time required to perform the scan. What is needed is a method to reduce the amount of memory required per block during block allocation testing to reduce the number of passes required for testing, and thus to reduce the amount of time the storage is unavailable.
The previous testing method is also unable to test for certain kinds of conflicts. For example, the method cannot determine when there are two different pointers improperly pointing to the same block. Therefore, what is also needed is a way to more thoroughly test the allocation of the blocks.